import com.sun.xml.internal.ws.api.message.Header;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-03-21
 * Time: 20:24
 */

public class TestDemo3 {
    public static List<String> topKFrequent(String[] words, int k) {
        //使用Map 存储单词出现的频率
        HashMap<String,Integer> map = new HashMap<>();
        for (String s:words) {
            if(map.get(s)==null){
                map.put(s,1);
            }else{
                int value = map.get(s);
                map.put(s,value+1);
            }
        }
        //创建小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o1.getKey().compareTo(o2.getKey());
                }
                return o1.getValue()- o2.getValue();
            }
        });
        //遍历Map，topK
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
             if(minHeap.size()<k){
                 minHeap.offer(entry);
            }else{
                 //此时说明堆中已经放满了K个元素，堆顶元素与当前元素进行比较
                 Map.Entry<String,Integer> top = minHeap.peek();
                 //如果次数相同，就比较单词大小，将较小的单词放入堆中。（按字典序排列）
                 if(top.getValue().compareTo(entry.getValue())==0){
                     if(top.getKey().compareTo(entry.getKey())>0){
                         minHeap.poll();
                         minHeap.offer(entry);
                     }
                 }else{ //如果次数不相同，就比较堆顶元素的次数与当前元素的次数，将次数多的放入堆中。
                     if(top.getValue().compareTo(entry.getValue())<0){
                         minHeap.poll();
                         minHeap.offer(entry);
                     }
                 }
             }
        }
        List<String> list = new ArrayList<>();
        //对前k个元素进行逆置
        for(int i=0;i<k;i++){
            Map.Entry<String,Integer> top = minHeap.poll();
            list.add(top.getKey());
        }
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        String[] worlds = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        List<String> ret = topKFrequent(worlds,4);
        System.out.println(ret);
    }






    public int search(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        int count = 0;
        for(int num:nums){
            if(map.get(num)==null){
                map.put(num,0);
            }else{
                int val = map.get(num);
                if(map.containsKey(target)){
                    map.put(num,val+1);
                }
            }
            count = map.get(num);
        }
        return count;
    }

    public static int func2(int[] array){
        Set<Integer> set = new HashSet<>();
        for (int s:array) {
            if(set.contains(s)){
                return s;
            }
            set.add(s);
        }
        return -1;
    }
    public static Set<Integer> func1(int[] array){
        Set<Integer> set = new HashSet<>();
        for (int s:array) {
            set.add(s);
        }
        return set;
    }

    //key:关键字，value：出现的次数
    public static Map<Integer,Integer> func(int[] array){
        Map<Integer,Integer> map = new HashMap<>();
        //判断array元素是否在map中，如果不在就是1，在就在原来的基础上+1
        for (int s:array) {
            //如果map 中没有那个数，次数就是1,
            if(map.get(s)==null){
                map.put(s,1);
            }else { //如果有，就在原来的基础上+1
                int val = map.get(s); //先获取当期数在map中的次数
                map.put(s,val+1);
            }
        }
        return map;
    }

    public static void main9(String[] args) {
        int[] array = new int[1_0000];
        Random random = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt(1000);
        }
        Map<Integer,Integer> map = func(array);
        System.out.println(map);

        Set<Integer> set = func1(array);
        System.out.println(set);
        int ret= func2(array);
        System.out.println(ret);
    }

    public static void main8(String[] args) {
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        System.out.println(set);
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }


    public static void main7(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        map.put("hello",4);
        map.put("abc",6);
        map.put("csdn",3);
        map.put(null,null);
        System.out.println(map);
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        for (Map.Entry<String,Integer> entry:entrySet) {
            System.out.println(entry.getKey()+"->"+entry.getValue());
        }
    }

    public static void main6(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        map.put("hello",4);
        map.put("abc",6);
        map.put("csdn",3);
        System.out.println(map);
        Collection<Integer> collection = map.values();
        System.out.println(collection);
    }

    public static void main5(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        map.put("hello",4);
        map.put("abc",6);
        map.put("csdn",3); //put 在存储元素时，要注意 key 如果相同，value值会被覆盖
        map.put("csdn",9);
        System.out.println(map); //Map中存放键值对的Key是唯一的，value是可以重复的
        Set<String> set = map.keySet(); //Set 集合中存储的元素都是不重复的
        System.out.println(set);
    }

    public static void main4(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        map.put("hello",4);
        map.put("abc",6);
        map.put("csdn",3);
        System.out.println(map);
        Integer ret = map.remove("abc");
        System.out.println(ret);
        System.out.println(map);
    }

    public static void main3(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        map.put("hello",4);
        map.put("csdn",3);
        System.out.println(map.getOrDefault("def",66));
        System.out.println(map.getOrDefault("csdn",99));
    }

    public static void main2(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        map.put("hello",4);
        map.put("csdn",3);
        map.put("abc",6);
        int ret = map.get("csdn");
        System.out.println(ret);
        System.out.println(map.get("def"));//如果 key 值不存在，获取的value值就是 null
        System.out.println(map.getOrDefault("def",66));//如果 key 值不存在，获取的value值就是 null
        System.out.println(map.getOrDefault("csdn",66));//如果 key 值不存在，获取的value值就是 null
    }

    public static void main1(String[] args) {
        Map<String,Integer> map = new HashMap<>();
        map.put("hello",4);
        map.put("def",1);
        map.put("csdn",3);
        map.put("abc",6);
        System.out.println(map);
    }
}
